#include <bits/stdc++.h>

using namespace std;

// 计数质数
// 给定整数n，返回小于非负整数n的质数的数量
// 测试链接 : https://leetcode.cn/problems/count-primes/

class Solution 
{
public:
    int countPrimes(int n) 
    {
        if(n == 0) return 0;
        return ehrlich(n - 1);
    }

	// 埃氏筛统计0 ~ n范围内的质数个数
	// 时间复杂度O(n * log(logn))
    int ehrlich(int n)
    {
		// visit[i] = true，代表i是合数
		// visit[i] = false，代表i是质数
		// 初始时认为0~n所有数都是质数
        bool visit[n + 1];
        memset(visit, 0, sizeof visit);
        for(int i = 2; i * i <= n; ++i)
        {
            if(!visit[i])
            {
                for(int j = i * i; j <= n; j += i)
                {
                    visit[j] = true;
                }
            }
        }
        int cnt = 0;
        for(int i = 2; i <= n; ++i) 
        {
            if(!visit[i]) ++cnt; // 此时i就是质数，可以收集，也可以计数
        }
        return cnt;
    }

	// 只是计数的话
	// 埃氏筛还能改进
    int ehrlich2(int n)
    {
        if(n <= 1) return 0;
		// visit[i] = true，代表i是合数
		// visit[i] = false，代表i是质数
		// 初始时认为0~n所有数都是质数
        bool visit[n + 1];
        memset(visit, 0, sizeof visit);
		// 先把所有的偶数去掉，但是算上2
		// 估计的质数数量，如果发现更多合数，那么cnt--
        int cnt = (n + 1) / 2;
        for(int i = 3; i * i <= n; i += 2)
        {
            if(!visit[i])
            {
                for(int j = i * i; j <= n; j += 2 * i)
                {
                    if(!visit[j])
                    {
                        visit[j] = true;
                        --cnt;
                    }
                }
            }
        }
        return cnt;
    }

	// 欧拉筛统计0 ~ n范围内的质数个数
	// 时间复杂度O(n)
    int euler(int n)
    {
		// visit[i] = true，代表i是合数
		// visit[i] = false，代表i是质数
		// 初始时认为0~n所有数都是质数
        bool visit[n + 1];
        memset(visit, 0, sizeof visit);
        // prime收集所有的质数，收集的个数是cnt
        int prime[n / 2 + 1];
        int cnt = 0;
        for(int i = 2; i <= n; ++i)
        {
            if(!visit[i]) prime[cnt++] = i;
            for(int j = 0; j < cnt; ++j)
            {
                if(i * prime[j] > n) break;
                visit[i * prime[j]] = true;
                if(i % prime[j] == 0) break;
            }
        }
        return cnt;
    }
};


class Solution 
{
public:
    int countPrimes(int n) 
    {
        if(n == 0) return n;
        return euler(n - 1);
    }

	// 埃氏筛统计0 ~ n范围内的质数个数
	// 时间复杂度O(n * log(logn))
    int ehrlich(int n)
    {
		// visit[i] = true，代表i是合数
		// visit[i] = false，代表i是质数
		// 初始时认为0~n所有数都是质数
        bool visit[n + 1];
        memset(visit, 0, sizeof visit);
        int cnt = 0;
        for(long i = 2; i <= n; ++i)
        {
            if(!visit[i])
            {
                // 此时i就是质数，可以收集，也可以计数
                ++cnt;
                for(long j = i * i; j <= n; j += i)
                {
                    visit[j] = true;
                }
            }
        }
        return cnt;
    }

	// 欧拉筛统计0 ~ n范围内的质数个数
	// 时间复杂度O(n)
    int euler(int n)
    {
		// visit[i] = true，代表i是合数
		// visit[i] = false，代表i是质数
		// 初始时认为0~n所有数都是质数
        bool visit[n + 1];
        memset(visit, 0, sizeof visit);
        int cnt = 0;
        int prime[n / 2 + 1];
        for(int i = 2; i <= n; ++i)
        {
            if(!visit[i]) prime[cnt++] = i;
            for(int j = 0; i * prime[j] <= n; ++j)
            {
                visit[i * prime[j]] = true;
                if(i % prime[j] == 0) break;
            }
        }
        return cnt;
    }
};